package segmentTreeWithoutLazy;

//线段树节点
class Tree {
	public int l; // 节点表示区间的左界
	public int r; // 节点表示区间的右届
	public int d; // 节点数据
	public Tree(int l, int r) {
		this.l = l;
		this.r = r;
	}
}

public class Main {
	// 数据长度
	public static int N = 10;
	// 线段树原数组，下标从1开始计算
	public static int[] a = { 0, 1, 4, 5, 8, 6, 2, 3, 9, 10, 7 };
	// 线段树，数组表示，长度必须为原数组4倍
	public static Tree[] t = new Tree[N * 4+1];
	// 返回左儿子编号，参数p为父节点编号
	public static int lc(int p) {
		// 左儿子编号p*2
		return p << 1; // 位运算提高效率
	}
	// 返回右儿子编号，参数p为父节点编号
	public static int rc(int p) {
		// 右儿子编号p*2+1
		return p << 1 | 1; // 位运算提高效率
	}
	// 构建线段树
	// 参数p节点编号
	// 参数l，r表示节点k指向的区间[l,r]
	public static void build(int p, int l, int r) {
		// 实例化节点
		t[p] = new Tree(l, r);
		// l==r则当前节点为叶子，直接存值
		// 叶子节点的l对应原数据的下标
		if (l == r) {
			t[p].d = a[l];
			return;
		}
		// 折半找区间[l,r]的中点
		int mid = (l + r) >> 1;
		int lc = lc(p);
		int rc = rc(p);
		// 左儿子递归建树
		build(lc, l, mid);
		// 右儿子递归建树
		build(rc, mid + 1, r);
		// 从下往上传递区间值，放入节点
		// 此处决定线段树维护区间和或最大值或最小值
		pushUp(p);
	}

	// 从下往上传递区间值，放入节点
	// 此处的p是叶子节点
	private static void pushUp(int p) {
		// 维护区间和情况
		// t[p].data = t[lc(p)].data + t[rc(p)].data;

		// 维护最小值情况
		// t[p].data = Math.min(t[lc(p)].data,t[rc(p)].data);

		// 维护最大值情况
		t[p].d = Math.max(t[lc(p)].d, t[rc(p)].d);
	}

	// 更新线段树节点（单点更新）
	// 参数p节点编号
	// 参数i表示将a[i]更新为v
	public static void update(int p, int i, int v) {
		// 找到了a[i]
		if (t[p].l == t[p].r && t[p].l == i) {
			t[p].d = v;
			return;
		}
		// 折半找区间[t[p].l,t[p].r]的中点
		int mid = (t[p].l + t[p].r) >> 1;
		int lc = lc(p); // 左子节点下标
		int rc = rc(p); // 右子节点下标
		if (i <= mid)
			update(lc, i, v); // 左子树更新
		else
			update(rc, i, v); // 右子树更新
		// 从下往上更新区间值，放入节点
		// 此处决定线段树维护区间和或最大值或最小值
		pushUp(p);
	}

	// 查询线段树（不带lazy标记的情况）
	// 参数p节点编号
	// 参数l，r表示求解的（区间和或最大值或最小值）区间[l,r]
	public static int query(int p, int l, int r) {
		// 1、查询区间覆盖节点区间，返回节点值（区简解）
		if (t[p].l >= l && t[p].r <= r) {
			return t[p].d;
		}

		// 折半找节点区间[segTree[k].l,segTree[k].r]的中点
		int mid = (t[p].l + t[p].r) >> 1;
		// 计算节点的左右子节点编号
		int lc = lc(p);
		int rc = rc(p);

		// ans变量保存区间[l,r]答案（查询区间最大值）
		int ans = Integer.MIN_VALUE;
		// ans变量保存区间[l,r]答案（查询区间最小值）
		// int ans=Integer.MAX_VALUE;
		// ans变量保存区间[l,r]答案（查询区间和）
		// int ans = 0;

		// 查询区间最大值的情况
		// l与左子树有重叠，则进入左子树递归查询
		if (l <= mid)
			ans = Math.max(ans, query(lc, l, r));
		// r与右子树有重叠，则进入左子树递归查询
		if (r > mid)
			ans = Math.max(ans, query(rc, l, r));

		// 查询区间最小值的情况
		// l与左子树有重叠，则进入左子树递归查询
//			if(l<=mid)
//				ans = Math.min(ans,query(lc,l,r));
//			//r与右子树有重叠，则进入左子树递归查询
//			if(r>mid)
//				ans = Math.min(ans,query(rc,l,r));

		// 查询区间和的情况
		// l与左子树有重叠，则进入左子树递归查询
//			if(l<=mid)
//				ans += query(lc,l,r);
//			//r与右子树有重叠，则进入左子树递归查询
//			if(r>mid)
//				ans += query(rc,l,r);
		return ans;
	}

	public static void main(String[] args) {
		// 构建线段树
		build(1, 1, 10);
		// 更新线段树
		System.out.println("更新节点1的值为11:");
		update(1, 1, 11);

		System.out.println("查询区间[1,10]:");
		System.out.println(query(1, 1, 10));

		System.out.println("查询区间[1,9]:");
		System.out.println(query(1, 1, 9));

		System.out.println("查询区间[1,8]:");
		System.out.println(query(1, 1, 8));

		System.out.println("查询区间[9,10]:");
		System.out.println(query(1, 9, 10));

		System.out.println("查询区间[3,7]:");
		System.out.println(query(1, 3, 7));

		System.out.println("查询区间[6,7]:");
		System.out.println(query(1, 6, 7));
	}

}
